//
// Description: 130. 被围绕的区域
// Created by Loading on 2025/5/26.
//

#include <bits/stdc++.h>

using namespace std;

void solve(vector<vector<char>> &board) {
    int m = board.size();
    int n = board[0].size();


    function<void(int, int)> dfs = [&](int i, int j) {
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') {
            return;
        }
        // 遍历到'O'的位置，未被围绕，标记为'#'
        board[i][j] = '#';
        // 四个方向搜索
        dfs(i - 1, j);
        dfs(i + 1, j);
        dfs(i, j - 1);
        dfs(i, j + 1);
    };

    // 第一列和最后一列遍历未被围绕的'O'
    for (int i = 0; i < m; ++i) {
        dfs(i, 0);
        dfs(i, n - 1);
    }
    // 第一行和最后一行遍历未被围绕的'O'
    for (int i = 1; i < n - 1; ++i) {
        dfs(0, i);
        dfs(m - 1, i);
    }

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            // 遍历完成后仍然存在'O'，则可以捕获
            if (board[i][j] == 'O') {
                board[i][j] = 'X';
            } else if (board[i][j] == '#') { // 将所有未被围绕的'O'置回
                board[i][j] = 'O';
            }
        }
    }
}

int main() {
    vector<vector<char>> board = {
            {'X', 'X', 'X', 'X'},
            {'X', 'O', 'O', 'X'},
            {'X', 'X', 'O', 'X'},
            {'X', 'O', 'X', 'X'}
    };

    solve(board);

    for (auto &v : board) {
        for (auto &x : v) {
            cout << x << ' ';
        }
        cout << endl;
    }

    return 0;
}
